Effective and efficient itemset pattern summarization: regression-based approaches
Ruoming Jin
Muad Abu-Ata
Yang Xiang
Ning Ruan
In this paper, we propose a set of novel regression-based approaches to effectively and efficiently summarize frequent itemset patterns. Specifically, we show that the problem of minimizing the restoration error for a set of itemsets based on a probabilistic model corresponds to a <i>non-linear regression problem</i>. We show that under certain conditions, we can transform the nonlinear regression problem to a <i>linear regression problem</i>. We propose two new methods, <i>k-regression</i> and <i>tree-regression</i>, to partition the entire collection of frequent itemsets in order to minimize the restoration error. The K-regression approach, employing a K-means type clustering method, guarantees that the total restoration error achieves a local minimum. The tree-regression approach employs a decision-tree type of top-down partition process. In addition, we discuss alternatives to estimate the frequency for the collection of itemsets being covered by the k representative itemsets. The experimental evaluation on both real and synthetic datasets demonstrates that our approaches significantly improve the summarization performance in terms of both accuracy (restoration error), and computational cost.
